package com.ycy.leetcode.dongtaiguihua;

import org.junit.Test;

public class BeiBao {

  @Test
  public void test() {
    //https://blog.csdn.net/qq_16234613/article/details/52235082

    int[] w = {5, 4, 7, 2, 6};
    int[] value = {12, 3, 10, 3, 6};

    int bag = 15;

    int[][] dp = new int[w.length][bag + 1];

    //初始化 矩阵第一排
    for (int j = 0; j < bag + 1; j++) {
      dp[0][j] = w[0] <= j ? value[0] : 0;
    }

    for (int i = 1; i < value.length; i++) {
      for (int j = 0; j < bag + 1; j++) {
        if (j < w[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + value[i]);

        System.out.println(String.format(" i %s j %s v %s", i, j, dp[i][j]));

      }
    }
    System.out.println(dp[w.length - 1][bag]);
  }

}
